Graphe parfait

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux.

Un graphe ${\displaystyle G}$ est 1-parfait^[1] si son nombre chromatique (noté ${\displaystyle \chi (G)}$) est égal à la taille de sa plus grande clique (notée ${\displaystyle \omega (G)}$) : ${\displaystyle \chi (G)=\omega (G)}$. Dans ce cas, ${\displaystyle G}$ est parfait si et seulement si tous les sous graphes de ${\displaystyle G}$ sont 1-parfait.